BFS: Expansion List

Now that you’ve modeled the problem using a Map and a Planner class in C++, you'll start with the first part of the BFS algorithm. In this quiz, you’ll write the search function which will expand the cells with the lowest cost until the goal is reached.

For that, you will need to represent each cell with a triplet value [g, x, y] where g represents the total cost of expanding toward this cell, x is the row value, and y is the column value.

Your function should print the final triplet value of the goal once it expands towards it.

Multiple things to keep in mind while coding the search function

• As you expand towards a new cell, check if you have reached the goal; and once you reach it, print its triplet value.
• Actively check if you have reached a roadblock. If you do, stop expanding and print a message indicating that you have failed to reach the goal.
• Expand the cells with the lowest g value and store your expansions in an open vector. If two cells have equal g values, then you can to pick one of them to expand further.

Hint

Here's how the cells are being expanded with the BFS algorithm until the goal is reached:

Expansion #: 0

Open List:
[0 0 0 ]

Cell Picked:
[0 0 0]

Expansion #: 1

Open List:
[1 1 0 ]

Cell Picked:
[1 1 0]

Expansion #: 2

Open List:
[2 2 0 ]

Cell Picked:
[2 2 0]

Expansion #: 3

Open List:
[3 3 0 ]

Cell Picked:
[3 3 0]

Expansion #: 4

Open List:
[4 4 0 ]

Cell Picked:
[4 4 0]

Expansion #: 5

Open List:
[5 4 1 ]

Cell Picked:
[5 4 1]

Expansion #: 6

Open List:
[6 4 2 ]

Cell Picked:
[6 4 2]

Expansion #: 7

Open List:
[7 3 2 ]

Cell Picked:
[7 3 2]

Expansion #: 8

Open List:
[8 3 3 ],
[8 2 2 ]

Cell Picked:
[8 2 2]

Expansion #: 9

Open List:
[9 2 3 ],
[9 1 2 ],
[8 3 3 ]

Cell Picked:
[8 3 3]

Expansion #: 10

Open List:
[9 3 4 ],
[9 2 3 ],
[9 1 2 ]

Cell Picked:
[9 1 2]

Expansion #: 11

Open List:
[10 1 3 ],
[10 0 2 ],
[9 3 4 ],
[9 2 3 ]

Cell Picked:
[9 2 3]

Expansion #: 12

Open List:
[10 2 4 ],
[10 1 3 ],
[10 0 2 ],
[9 3 4 ]

Cell Picked:
[9 3 4]

Expansion #: 13

Open List:
[10 3 5 ],
[10 2 4 ],
[10 1 3 ],
[10 0 2 ]

Cell Picked:
[10 0 2]

Expansion #: 14

Open List:
[11 0 3 ],
[10 3 5 ],
[10 2 4 ],
[10 1 3 ]

Cell Picked:
[10 1 3]

Expansion #: 15

Open List:
[11 1 4 ],
[11 0 3 ],
[10 3 5 ],
[10 2 4 ]

Cell Picked:
[10 2 4]

Expansion #: 16

Open List:
[11 2 5 ],
[11 1 4 ],
[11 0 3 ],
[10 3 5 ]

Cell Picked:
[10 3 5]

Expansion #: 17

Open List:
[11 4 5 ],
[11 2 5 ],
[11 1 4 ],
[11 0 3 ]

Cell Picked:
[11 0 3]

Expansion #: 18

Open List:
[12 0 4 ],
[11 4 5 ],
[11 2 5 ],
[11 1 4 ]

Cell Picked:
[11 1 4]

Expansion #: 19

Open List:
[12 1 5 ],
[12 0 4 ],
[11 4 5 ],
[11 2 5 ]

Cell Picked:
[11 2 5]

Expansion #: 20

Open List:
[12 1 5 ],
[12 0 4 ],
[11 4 5 ]

Cell Picked:
[11 4 5]

Start Quiz:

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

// Map class
class Map {
public:
    const static int mapWidth = 6;
    const static int mapHeight = 5;
    vector<vector<int> > grid = {
        { 0, 1, 0, 0, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 0, 0, 0, 1, 1, 0 }
    };
};

// Planner class
class Planner : Map {
public:
    int start[2] = { 0, 0 };
    int goal[2] = { mapHeight - 1, mapWidth - 1 };
    int cost = 1;

    string movements_arrows[4] = { "^", "<", "v", ">" };

    vector<vector<int> > movements{
        { -1, 0 },
        { 0, -1 },
        { 1, 0 },
        { 0, 1 }
    };
};

// Template function to print 2D vectors of any type
template <typename T>
void print2DVector(T Vec)
{
    for (int i = 0; i < Vec.size(); ++i) {
        for (int j = 0; j < Vec[0].size(); ++j) {
            cout << Vec[i][j] << ' ';
        }
        cout << endl;
    }
}

/*#### TODO: Code the search function which will generate the expansion list ####*/
// You are only required to print the final triplet values
void search(Map map, Planner planner)
{
    
}

int main()
{
    // Instantiate map and planner objects
    Map map;
    Planner planner;

    // Search for the expansions
    search(map, planner);

    return 0;
}

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

// Map class
class Map {
public:
    const static int mapWidth = 6;
    const static int mapHeight = 5;
    vector<vector<int> > grid = {
        { 0, 1, 0, 0, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 0, 0, 0, 1, 1, 0 }
    };
};

// Planner class
class Planner : Map {
public:
    int start[2] = { 0, 0 };
    int goal[2] = { mapHeight - 1, mapWidth - 1 };
    int cost = 1;

    string movements_arrows[4] = { "^", "<", "v", ">" };

    vector<vector<int> > movements{
        { -1, 0 },
        { 0, -1 },
        { 1, 0 },
        { 0, 1 }
    };
};

// Template function to print 2D vectors of any type
template <typename T>
void print2DVector(T Vec)
{
    for (int i = 0; i < Vec.size(); ++i) {
        for (int j = 0; j < Vec[0].size(); ++j) {
            cout << Vec[i][j] << ' ';
        }
        cout << endl;
    }
}

// Search function which generates the expansions
void search(Map map, Planner planner)
{
    // Create a closed 2 array filled with 0s and first element 1
    vector<vector<int> > closed(map.mapHeight, vector<int>(map.mapWidth));
    closed[planner.start[0]][planner.start[1]] = 1;

    // Defined the triplet values
    int x = planner.start[0];
    int y = planner.start[1];
    int g = 0;

    // Store the expansions
    vector<vector<int> > open;
    open.push_back({ g, x, y });

    // Flags
    bool found = false;
    bool resign = false;

    int x2;
    int y2;

    // While I am still searching for the goal and the problem is solvable
    while (!found && !resign) {
        // Resign if no values in the open list and you can't expand anymore
        if (open.size() == 0) {
            resign = true;
            cout << "Failed to reach a goal" << endl;
        }
        // Keep expanding
        else {
            // Remove triplets from the open list
            sort(open.begin(), open.end());
            reverse(open.begin(), open.end());
            vector<int> next;
            // Stored the poped value into next
            next = open.back();
            open.pop_back();

            x = next[1];
            y = next[2];
            g = next[0];
            
            // Check if we reached the goal:
            if (x == planner.goal[0] && y == planner.goal[1]) {
                found = true;
                cout << "[" << g << ", " << x << ", " << y << "]" << endl;
            }

            //else expand new elements
            else {
                for (int i = 0; i < planner.movements.size(); i++) {
                    x2 = x + planner.movements[i][0];
                    y2 = y + planner.movements[i][1];
                    if (x2 >= 0 && x2 < map.grid.size() && y2 >= 0 && y2 < map.grid[0].size()) {
                        if (closed[x2][y2] == 0 and map.grid[x2][y2] == 0) {
                            int g2 = g + planner.cost;
                            open.push_back({ g2, x2, y2 });
                            closed[x2][y2] = 1;
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    // Instantiate map and planner objects
    Map map;
    Planner planner;

    // Search for the expansions
    search(map, planner);

    return 0;
}